# https://gitee.com/yueyinqiu5990/tj12413601/blob/master/assignment1/question3/interpolations/neville.py
import typing

from question3.interpolation_method import InterpolationMethod1d


class NevilleInterpolation(InterpolationMethod1d):
    def interpolate(
            self,
            points: typing.Iterable[tuple[float, float]]) \
            -> typing.Callable[[float], float]:
        points = list(points)
        if len(points) < 2:
            raise ValueError(f"Cannot do interpolation with {len(points)} point.")

        def f(x: float, left: int, right: int):
            if left == right:
                return points[left][1]
            without_right = f(x, left, right - 1)
            without_left = f(x, left + 1, right)
            x_left = points[left][0]
            x_right = points[right][0]
            without_right *= x - x_right
            without_left *= x - x_left
            return (without_right - without_left) / (x_left - x_right)

        def result_function(x: float):
            return f(x, 0, len(points) - 1)

        return result_function
